home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / ada / gwuada_9.zip / PRSERR.C < prev    next >
C/C++ Source or Header  |  1993-07-27  |  39KB  |  1,388 lines
  1. /*
  2.  * Copyright (C) 1985-1992  New York University
  3.  * 
  4.  * This file is part of the Ada/Ed-C system.  See the Ada/Ed README file for
  5.  * warranty (none) and distribution info and also the GNU General Public
  6.  * License for more details.
  7.  
  8.  */
  9. /********************************************************************
  10.  *                                    
  11.  *              *****************               
  12.  *              *  P R S E R R  
  13.  *              *****************             
  14.  *                                
  15.  *                 Written by                   
  16.  *               Brian Siritzky              
  17.  *                1983                 
  18.  *                                
  19.  ********************************************************************/
  20.  
  21. /********************************************************************/
  22.  
  23. /********************************************************************/
  24.  
  25. #include "hdr.h"
  26. #include "ada.h"
  27. #include "adalexp.h"
  28. #include "actionp.h"
  29. #include "pspansp.h"
  30. #include "errsp.h"
  31. #include "lookupp.h"
  32. #include "prsutilp.h"
  33. #include "recoverp.h"
  34. #include "makecorp.h"
  35. #include "prserrp.h"
  36.  
  37. static void get_poss_tok();
  38. static void get_next(int);
  39.  
  40. /*    
  41.  * Variables needed for scope and secondary recoveries
  42.  */
  43.  
  44. struct two_pool *closer_toksyms ;
  45. struct two_pool *closer_bottom ;
  46.  
  47. struct two_pool *POSS_TOK;
  48. /* struct prsstack **tokens; deleted on Sam's suggestion 12-11-84 */
  49. int    TOKSYMS[S_TOKSYMS], n_TOKSYMS;
  50. int    BACKUPTOKS = 0;
  51. int    MAX_CHECK = MIN_LEN ;
  52.  
  53. PCAND next_c, y, next_cand, CANDIDATES[C_BOUND];
  54. static PCAND tmp_cand,temp_cand;
  55. int    n_CANDIDATES[C_BOUND] ;
  56. int nps;
  57. int n_open_seq;
  58. int *open_seq;
  59. int n_closer_toksyms;
  60.  
  61. void prserr(struct prsstack *curtok)                            /*;prserr*/
  62. {
  63.  
  64.     /********************************************************************
  65.      *
  66.      * This routine is the syntactic error    recovery  routine.   It     at-
  67.      * tempts  to  correct    simple errors and when that is not possible,
  68.      * deletes tokens possibly to the left and to the right of the error
  69.      * point until the parse can safely resume.  The process is thus di-
  70.      * vided naturally into two  parts,  called  primary  and  secondary
  71.      * recovery.  Both primary and secondary recovery include efforts at
  72.      * "scope recovery": i.e.  the    closing     of  lexically    open  scopes
  73.      * through the insertion of one or more closer token sequences.     Ex-
  74.      * amples of such sequences are right parentheses, "END ;", and "END
  75.      * IF;".
  76.      * 
  77.      * Primary recovery consists of the simple corrections - merging to-
  78.      * kens,  substituting    a  token  (including a reserved word that is
  79.      * misspelled as an identifier), inserting a token, and     deleting  a
  80.      * token - along with scope recovery.
  81.      * 
  82.      * An attempt at simple correction at either the error token  or  at
  83.      * some parse stack element is called a trial.
  84.      * 
  85.      * For the first trial simple corrections are attempted at the token
  86.      * at which the error was detected (the error token), with the parse
  87.      * in the configuration obtaining just after  the  shifting  of     the
  88.      * previous  token. In order to back up to the succeeding trial, the
  89.      * top elements are peeled from the state and parse stacks, with the
  90.      * top element of the parse stack appended to the front of the input
  91.      * token sequence. Again attempts at simple correction are made. The
  92.      * process  is    repeated  until     the determined extent of the backup
  93.      * move has been accomplished.
  94.      * 
  95.      * The criterion by which the effectiveness of a  simple  correction
  96.      * candidate is measured is the distance it allows the parse to pro-
  97.      * gress into the forward context (up to  MAX_LOOK_AHEAD  =  25     to-
  98.      * kens).   During  the     simple correction trials we gather together
  99.      * the CANDIDATES that allow the parse    to  progress  the  furthest,
  100.      * provided  that  an  advance of at least MIN_CHECK is accomplished
  101.      * (if not, then CANDIDATES is empty and simple     correction  fails).
  102.      * If  CANDIDATES is not empty, it is pruned in accordance with cer-
  103.      * tain restrictions described below, and then one of them is chosen
  104.      * as the appropriate correction provided that a condition described
  105.      * below is satisfied.
  106.      * 
  107.      * No attempt is made to delete or substitute for a nonterminal.
  108.      * 
  109.      * If no simple correction is chosen, scope recovery is attempted at
  110.      * each     point    at  which  simple  recovery was attempted. The scope
  111.      * recovery procedure determines whether the insertion of a sequence
  112.      * of  scope  closers  allows the parse to progress MIN_LEN distance
  113.      * into the forward context.  If  so,  this  multiple  insertion  is
  114.      * chosen as the correction candidate.
  115.      * 
  116.      * If scope recovery also fails, then secondary recovery is invoked.
  117.      * The    parse  is  restored  to the configuration obtaining upon en-
  118.      * trance to PRSERR, and each parse stack element is tested - in se-
  119.      * quence from the top - to see whether parsing can resume from that
  120.      * point, perhaps with the inclusion of one or more closer token se-
  121.      * quences.  The  extent  of  the  advance required in order for the
  122.      * parse to be regarded as successfully     resumed  depends  upon     the
  123.      * current token, but is at least MIN_LEN.
  124.      * 
  125.      * If secondary recovery at the current token does not    succeed,  it
  126.      * is  ignored    and  the next one obtained and the same check is re-
  127.      * peated. Eventually, there must be an input for  which  the  parse
  128.      * can    continue, because the end of file token, EOFT, is compatible
  129.      * with a state on the state stack.
  130.      * 
  131.      * When the recovery point is found,  control  is  returned  to     the
  132.      * parser.  It is assured that parsing can continue beyond the error
  133.      * token.
  134.      * 
  135.      ********************************************************************/
  136.  
  137.     /* PARSE STACK and BINARY TUPLE STRUCTURES */
  138.     typedef struct two_pool *TUPLE;
  139.  
  140.  
  141.     struct prsstack *ERROR_TOKEN;
  142.     struct prsstack *oldprevtok;/* Saved for scope and secondary recovery */
  143.     struct prsstack *tmp_ps;
  144.  
  145.     TUPLE STATE_STACK = NULL;
  146.     TUPLE prs_toks = NULL;    /* Used to determine the no of */
  147.     TUPLE tmp_tp;            /* trials to be performed */
  148.     /* Used for freeing storage */
  149.     TUPLE prs_stack_syms = NULL;
  150.  
  151.     int pb;            /* Used as a flag to check for a parse block */
  152.     int threshold,        /* Used to prune candidates */
  153.     exists;        /* Flag used in list searching */
  154.  
  155.     short trials,        /* Number of trials performed    */
  156.       j, r, trial,
  157.       i,            /* Loop and auxilliary        */
  158.       bk, cc, x, si ;
  159.  
  160.     int n_PARSE_STACK;
  161.     int save_n_TOKSYMS ;
  162.     struct two_pool *states;
  163.  
  164.     int        n_single_cand_modes, total_CANDIDATES;
  165.     int        n_STATE_STACK, n_sta_stack;
  166.  
  167.     ERROR_TOKEN = copytoken (curtok);
  168.     MAX_CHECK = MIN_LEN;
  169.  
  170.     /* ERR_MSGS = NULL ; CLOSER_TOKSYMS = NULL ; */
  171.  
  172.     copystack (sta_stack, &STATE_STACK, &n_sta_stack);
  173.     /* save for scope and secondary recovery */
  174.     if (PREVTOK != NULL)
  175.         oldprevtok = copytoken (PREVTOK);
  176.  
  177.     n_STATE_STACK = n_sta_stack;
  178.  
  179.     BACKUPTOKS = 0;
  180.  
  181.     get_next (MAX_LOOK_AHEAD);
  182.  
  183.     /* prs_stack_syms := [r(1) : r in PRS_STACK];            
  184.      * Loop over PRS_STACK, collecting the symbols in a list  
  185.      * headed by prs_stack_syms. While doing this, count up the 
  186.      * number of elements in the parse stack, keeping this in  
  187.      * n_PARSE_STACK and nps                   
  188.      */
  189.  
  190.     n_PARSE_STACK = 0;
  191.  
  192.     if ((tmp_ps= prs_stack) == NULL)/* Check for empty stacks */
  193.         prs_stack_syms = NULL;
  194.     else {                /* otherwise copy the list */
  195.         /* Treat the first element as a special case */
  196.         tmp_tp = prs_stack_syms = TALLOC ();
  197.         tmp_tp -> link = NULL;
  198.         tmp_tp -> val.state = tmp_ps -> symbol;
  199.         n_PARSE_STACK = 1;
  200.         /* Loop over the rest of the stack */
  201.         while (tmp_ps -> prev != NULL) {
  202.             tmp_tp -> link = TALLOC ();
  203.             tmp_tp = tmp_tp -> link;
  204.             tmp_ps = tmp_ps -> prev;
  205.             tmp_tp -> val.state = tmp_ps -> symbol;
  206.             n_PARSE_STACK++;
  207.         }            /* while */
  208.         tmp_tp -> link = NULL;
  209.     }                /* else */
  210.     nps = n_PARSE_STACK;
  211.  
  212.     /* * TOKSYMS := [t(1) : t in TOKENS];             
  213.      * Loop over TOKENS, collecting the symbols in a list    
  214.      * The integer tokind is a count of the number of     
  215.      * elements in the array tokens.              
  216.      *
  217.      * Note that tokens[tokind] is the next token, so we must
  218.      * reverse the order of TOKSYMS                            
  219.      */
  220.  
  221.     /* Put the current token at the top of the token stack */
  222.     tokens[tokind = (tokind + 1) % toksiz] = curtok;
  223.     i = 0;
  224.     j = tokbottom;
  225.  
  226.     for (;;) {
  227.         TOKSYMS[i] = tokens[j]->symbol;
  228.         if (j == tokind)
  229.             break;
  230.         j = (j + 1) % toksiz;
  231.         i++;
  232.     }
  233.  
  234.     save_n_TOKSYMS    = n_TOKSYMS = (toksiz